#include <vector>
#include <stack>
using namespace std;

// 具体思路： 使用单调栈
// 1. 遍历温度数组，使用栈存储温度的下标
// 2. 如果栈不为空，把当前元素和栈顶的元素比较
//   - 如果当前元素大于栈顶元素，说明找到了第一个更高温度，计算天数差，更新结果数组
//  - 如果当前元素小于等于栈顶元素，说明还没有找到更高温度，继续入栈
// 3. 最后返回结果数组
// 细节： 结果数组初始化为0，因为如果没有更高温度，结果就是0
// 就是维护栈顶的元素是最小的，遇到更大的就出栈计算差值   这个差值是属于栈顶元素的结果
class Solution
{
public:
    vector<int> dailyTemperatures(vector<int> &temperatures)
    { 
        vector<int> res(temperatures.size(), 0); // 结果数组,用0填充
        stack<int> st;
        for (int i = 0; i < temperatures.size(); ++i)
        {
            // 1. 如果栈不为空，把当前元素和栈顶的元素比较
            while (!st.empty() && temperatures[i] > temperatures[st.top( )])
            {
                int index = st.top();
                res[index] = i - index;
                st.top();
            }
            st.push(i);
        }
        return res;
    }
};